In recent years, a technique of group signature has been proposed in the fields of encryption and signature. The group signature technique is a technique for authenticating whether a signer belongs to a group which has a certain authorization. Which member in the group the signer is can be anonymized. This technique has an advantage that an authorized person can prevent a user from remaining anonymous if there is any problem, which makes it possible to prevent abuse of anonymity.
A group signature technique is disclosed, for example, in the following literatures (PTL 1, NPTL 1 to NPTL 4). NPTL 1 discloses a basic algorithm to generate and verify a group signature.
Further, NPTL 1 discloses a small-sized circuit that generates a group signature at high speed. A signature generation apparatus disclosed in NPTL 1 includes an elliptic curve operation circuit, an RSA operation circuit, and a hash operation circuit, and these circuits are connected by a low band bus. By appropriately adjusting the number of each operation circuit, it is possible to execute each operation of an elliptic curve operation, an RSA operation, and a hash operation in parallel and to increase the speed of signature generation without dramatically increasing the size of the circuits.
Incidentally, in the implementation of encryption, it is important to take measures against side-channel attacks which obtain secret information from the operation status of an apparatus which is performing encryption processing. The most typical method of the side-channel attacks that is known is to find out the value of a private key from waveforms of leakage electromagnetic waves or power consumption waveforms of a circuit.
Various methods have been known as the side-channel attacks. Regarding public key encryption such as RSA encryption and elliptic encryption, a method called a timing attack which uses the fact that the operation time changes according to the value of each bit of the key, and a method called SPA (Simple Power Analysis) that uses the fact that the magnitude of power consumption changes according to the value of each bit of the key are popular and the most dangerous.
Well-known countermeasures against the timing attack or the SPA include a method of adding and executing a pseudo operation to prevent the operation time or power consumption from being varied depending on the values of the key, and a method of adding a circuit for operation using a random value to achieve parallel operations. As long as a public key encryption circuit is used, the principle of the countermeasures that are used is substantially the same both in RSA encryption and in elliptic encryption.
For example, NPTL 2 and PTL 2 to PTL 4 disclose countermeasure techniques against side-channel attacks. NPTL 2 discloses a method of side-channel attacks against an RSA encryption circuit, and measures to take against the attack. PTL 2 discloses a countermeasure technique against side-channel attacks for a scalar operation on an elliptic curve (paragraphs 0022-0027, 0139-0145).
PTL 3 discloses performing a simultaneous operation of an inverse transform operation, to execute a routine to prevent side-channel attacks (paragraphs 0010-0012, 0035-0041). PTL 3 takes measures using an inverse transform operation (complementary operation), and uses a random value for disturbance of an operation time length. PTL 4 discloses masking an intermediate variable value with a random value as a countermeasure technique against side-channel attacks.